{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Least Number of Unique Integers after K Removals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLeastNumOfUniqueInts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同整数的最少数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> 和一个整数 <code>k</code> 。现需要从数组中恰好移除 <code>k</code> 个元素，请找出移除后数组中不同整数的最少数目。</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [5,5,4], k = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>移除 1 个 4 ，数组中只剩下 5 一种整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [4,3,1,1,3,3,2], k = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length&nbsp;&lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10^9</code></li>\n",
    "\t<li><code>0 &lt;= k&nbsp;&lt;= arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [least-number-of-unique-integers-after-k-removals](https://leetcode.cn/problems/least-number-of-unique-integers-after-k-removals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [least-number-of-unique-integers-after-k-removals](https://leetcode.cn/problems/least-number-of-unique-integers-after-k-removals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,5,4]\\n1', '[4,3,1,1,3,3,2]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        if k>=n:\n",
    "            return 0\n",
    "\n",
    "        cnt=Counter(arr)\n",
    "        values=list(cnt.values())\n",
    "        values.sort()\n",
    "        for i, v in enumerate(values):\n",
    "            if k>=v:\n",
    "                k-=v\n",
    "                continue\n",
    "            else:\n",
    "                return len(values)-i\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        lst=sorted(list(Counter(arr).values()))\n",
    "        n=len(lst)\n",
    "        i=0\n",
    "        while k>0 and i<n:\n",
    "            if k<lst[i]:\n",
    "                return n-i\n",
    "            else:\n",
    "                k-=lst[i]\n",
    "                i+=1\n",
    "        return n-i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        freq = list(Counter(arr).values())\n",
    "        freq.sort()\n",
    "        res = len(freq)\n",
    "        for j in freq:      #贪心，先消耗掉freq小的。容易，划算\n",
    "            if j <= k:\n",
    "                k -= j\n",
    "                res -= 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        c = Counter(arr)\n",
    "        l = sorted(c.values())\n",
    "        ct = len(c)\n",
    "        for idx, val in enumerate(l):\n",
    "            if k >= val:\n",
    "                k -= val\n",
    "                ct -= 1\n",
    "            else:\n",
    "                break\n",
    "        return ct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        cnt=Counter(arr)\n",
    "        temp=sorted(cnt.values())\n",
    "        cur=0\n",
    "        while k>0:\n",
    "            if temp[cur]>=k:\n",
    "                temp[cur]-=k\n",
    "                k=0\n",
    "            else :\n",
    "                k-=temp[cur]\n",
    "                temp[cur]=0\n",
    "                cur+=1\n",
    "        return sum([1 if i>0 else 0 for i in temp])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        count = collections.Counter(arr)      \n",
    "        sortv = sorted(count.values())\n",
    "        for ind, ele in enumerate(sortv):\n",
    "            k-=ele\n",
    "            if k==0:\n",
    "                return len(sortv)-(ind+1)\n",
    "            elif k<0:\n",
    "                return len(sortv)-ind\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        count = collections.Counter(arr)      \n",
    "        sortv = sorted(count.values())\n",
    "        for ind, ele in enumerate(sortv):\n",
    "            k-=ele\n",
    "            if k==0:\n",
    "                return len(sortv)-(ind+1)\n",
    "            elif k<0:\n",
    "                return len(sortv)-ind\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        count = collections.Counter(arr)      \n",
    "        sortv = sorted(count.values())\n",
    "        for ind, ele in enumerate(sortv):\n",
    "            k-=ele\n",
    "            if k==0:\n",
    "                return len(sortv)-(ind+1)\n",
    "            elif k<0:\n",
    "                return len(sortv)-ind\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        arr_dict = dict(Counter(arr))\n",
    "        num_repeat = [value for key,value in arr_dict.items()]\n",
    "        num_repeat.sort()\n",
    "        num_repeat_sorted = num_repeat.copy()\n",
    "        sum = 0\n",
    "        # dic = Counter(arr)\n",
    "\n",
    "        # num_repeat_sorted = sorted(list(dic.values()))\n",
    "        \n",
    "        #len_c = len(count_list)\n",
    "        for i in range(len(num_repeat_sorted)):\n",
    "            if k-num_repeat_sorted[i]>0:\n",
    "                k=k-num_repeat_sorted[i]\n",
    "            elif k-num_repeat_sorted[i]==0:\n",
    "                return len(num_repeat_sorted)-i-1\n",
    "            else:\n",
    "                return len(num_repeat_sorted)-i\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "#         dic = Counter(arr)\n",
    "\n",
    "#         count_list = sorted(list(dic.values()))\n",
    "        \n",
    "#         len_c = len(count_list)\n",
    "  \n",
    "#         for i in range(len_c):\n",
    "#             if k - count_list[i] > 0:\n",
    "#                 k = k - count_list[i]\n",
    "#             elif k - count_list[i] == 0:\n",
    "#                 return len_c - i - 1\n",
    "#             else:\n",
    "#                 return len_c - i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        num_n_dict = collections.defaultdict(int)\n",
    "        for num in arr:\n",
    "            num_n_dict[num] += 1\n",
    "        num_n_list = [[k, v] for k, v in num_n_dict.items()]\n",
    "        num_n_list.sort(key=lambda x: x[1])\n",
    "        i = 0\n",
    "        while k:\n",
    "            if num_n_list[i][1] <= k:\n",
    "                k -= num_n_list[i][1]\n",
    "                num_n_list[i][1] = 0\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        re = 0\n",
    "        for num_n in num_n_list:\n",
    "            if num_n[1]:\n",
    "                re += 1\n",
    "        return re\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    贪心\n",
    "    \"\"\"\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        arr_counter = Counter(arr)        \n",
    "        arr_counter = [[key, v] for key, v in arr_counter.items()]\n",
    "        arr_counter = sorted(arr_counter, key=lambda x: x[1])\n",
    "        i = 0\n",
    "        while i < len(arr_counter):\n",
    "            k -= arr_counter[i][1] # 减掉\n",
    "            if k < 0: return len(arr_counter) - i\n",
    "            if k == 0: return len(arr_counter) - (i+1)\n",
    "            i += 1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        n = len(set(arr))\n",
    "        for v in sorted(cnt.values()):\n",
    "            if v <= k:\n",
    "                k -= v\n",
    "                n -= 1\n",
    "            else:\n",
    "                break\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        count=Counter(arr)\n",
    "        countlist=[]\n",
    "        for key,v in count.items():\n",
    "            countlist.append([key,v])\n",
    "        countlist.sort(key=lambda x:x[1])\n",
    "        n=len(countlist)\n",
    "\n",
    "        for i in range(n):\n",
    "            k-=countlist[i][1]\n",
    "            if k<0:\n",
    "                return n-i\n",
    "            if k==0:\n",
    "                return n-i-1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        count = dict(Counter(arr))\n",
    "        len_arr = len(set(arr))\n",
    "        count_ = sorted(count, key=lambda x: count[x])\n",
    "        for i in count_:\n",
    "            if count[i] <= k:\n",
    "                len_arr -= 1\n",
    "                k -= count[i]\n",
    "            else:\n",
    "                break\n",
    "        return len_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        c = Counter(arr)\n",
    "        c = sorted(list(c.items()), key=lambda x:-x[1])\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < len(c) and cnt < n - k:\n",
    "            cnt += c[i][1]\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        lookup = defaultdict(int)\n",
    "        for a in arr:\n",
    "            lookup[a] += 1\n",
    "        res = sorted(lookup.items(), key= lambda x:x[1])\n",
    "        sum_index = []\n",
    "        for i in res:\n",
    "            if not sum_index:\n",
    "                sum_index.append(lookup[i[0]])\n",
    "            else:\n",
    "                sum_index.append(sum_index[-1] + lookup[i[0]])\n",
    "        # print(sum_index, res)\n",
    "        for i in range(len(sum_index)):\n",
    "            if sum_index[i] > k:\n",
    "                return len(res[i:])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dic_ = {}\n",
    "        for i in arr:\n",
    "            if i not in dic_:\n",
    "                dic_[i] = 1\n",
    "            else:\n",
    "                dic_[i] += 1\n",
    "        d = sorted(dic_.items(), key=lambda kv: kv[1])\n",
    "        print(d)\n",
    "        while k > 0:\n",
    "            if k >= d[0][1]:\n",
    "                k -= d[0][1]\n",
    "                d.pop(0)\n",
    "            else:\n",
    "                break\n",
    "        return len(d)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        if len(arr)<=k:return 0\n",
    "        cnt = collections.Counter(arr)\n",
    "        cnt = collections.deque(sorted(cnt.items(),key=lambda x:x[1]))\n",
    "        while k >= cnt[0][1] :\n",
    "            i,j = cnt.popleft()\n",
    "            k -=j\n",
    "        return len(cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        mm = Counter(arr)\n",
    "        mm = [[k, mm[k]] for k in mm.keys()]\n",
    "        mm.sort(key=lambda x: x[1])\n",
    "        ans = len(mm)\n",
    "        idx = 0\n",
    "        n = len(mm)\n",
    "\n",
    "        for kk, c in mm:\n",
    "            if c <= k:\n",
    "                k -= c\n",
    "                ans -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        # while idx < n:\n",
    "        #     if mm[idx][1] <= k:\n",
    "        #         ans -= 1\n",
    "        #         k -= mm[idx][1]\n",
    "        #     else:\n",
    "        #         break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        memory = {}\n",
    "        for each in arr:\n",
    "            if each in memory:\n",
    "                memory[each] += 1\n",
    "            else:\n",
    "                memory[each] = 1\n",
    "        record = sorted(memory.items(),key = lambda x:-x[1])\n",
    "        print(record)\n",
    "        rest = k\n",
    "        i = len(record) - 1\n",
    "        while i >= 0:\n",
    "            if rest - record[i][1] < 0:\n",
    "                break\n",
    "            else:\n",
    "                rest -= record[i][1]\n",
    "                record.pop()\n",
    "            \n",
    "            i -= 1\n",
    "        return len(record)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        lst = dict(Counter(arr))\n",
    "        print(lst)\n",
    "        lst = sorted(lst.values())\n",
    "        print(lst)\n",
    "        n = 0\n",
    "        for i in range(len(lst)):\n",
    "            if lst[i] <= k: \n",
    "                k -= lst[i]\n",
    "            else:\n",
    "                n += 1\n",
    "\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        tmp = dict()\n",
    "        for i in arr:\n",
    "            tmp[i] = tmp.get(i, 0) + 1\n",
    "        tmp2 = list()\n",
    "        for key, v in tmp.items():\n",
    "            tmp2.append([key, v])\n",
    "        tmp2.sort(key=lambda x:x[1])\n",
    "        i = 0\n",
    "        while k > 0:\n",
    "            if k >= tmp2[i][1]:\n",
    "                k -= tmp2[i][1]\n",
    "                tmp2[i][1] = 0\n",
    "            else:\n",
    "                tmp2[i][1] -= k\n",
    "                k = 0\n",
    "            i += 1\n",
    "        return sum(1 if x[1] != 0 else 0 for x in tmp2)\n",
    "        # return len(list(filter(lambda x:x[1] != 0, tmp2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        tmp = dict()\n",
    "        for i in arr:\n",
    "            tmp[i] = tmp.get(i, 0) + 1\n",
    "        tmp2 = list()\n",
    "        for key, v in tmp.items():\n",
    "            tmp2.append([key, v])\n",
    "        tmp2.sort(key=lambda x:x[1])\n",
    "        i = 0\n",
    "        while k > 0:\n",
    "            if k >= tmp2[i][1]:\n",
    "                k -= tmp2[i][1]\n",
    "                tmp2[i][1] = 0\n",
    "            else:\n",
    "                tmp2[i][1] -= k\n",
    "                k = 0\n",
    "            i += 1\n",
    "        return sum(1 if x[1] != 0 else 0 for x in tmp2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        memory = {}\n",
    "        for each in arr:\n",
    "            if each in memory:\n",
    "                memory[each] += 1\n",
    "            else:\n",
    "                memory[each] = 1\n",
    "        record = sorted(memory.items(),key = lambda x:-x[1])\n",
    "        print(record)\n",
    "        rest = k\n",
    "        i = len(record) - 1\n",
    "        while i >= 0:\n",
    "            if rest - record[i][1] < 0:\n",
    "                break\n",
    "            else:\n",
    "                rest -= record[i][1]\n",
    "                record.pop()\n",
    "            \n",
    "            i -= 1\n",
    "        return len(record)\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dict1={}\n",
    "        for i in arr:\n",
    "            if dict1.get(i) is None:\n",
    "                dict1[i]=1\n",
    "            else:\n",
    "                dict1[i]+=1\n",
    "        # print(dict1)\n",
    "        arr2=[]\n",
    "        for key1, v in dict1.items():\n",
    "            arr2.append((key1,v))\n",
    "        arr2.sort(key=lambda x:-x[1])\n",
    "        # print(arr2)\n",
    "        l3=[]\n",
    "        for index1 in arr2:\n",
    "            for index2 in range(index1[1]):\n",
    "                l3.append(index1[0])\n",
    "        # print(l3,k)\n",
    "        for j in range(k):\n",
    "            l3.pop()\n",
    "        return len(set(l3))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        for i in arr:\n",
    "            d[i] += 1\n",
    "        l = [[k, d[k]] for k in d.keys()]\n",
    "        l.sort(key = lambda x: x[1])\n",
    "        index = 0\n",
    "        while (k > 0) and (index < len(l)):\n",
    "            k -= l[index][1]\n",
    "            index += 1\n",
    "        if k < 0:\n",
    "            return len(l) - index + 1\n",
    "        else:\n",
    "            return len(l) - index\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        freq = Counter(arr)\n",
    "        freq = freq.most_common()[::-1]\n",
    "        ret = len(freq)\n",
    "        for _, f in freq:\n",
    "            if k >= f:\n",
    "                ret -= 1\n",
    "                k -= f \n",
    "            else:\n",
    "                break \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        c = Counter(arr)\n",
    "        result = len(c)\n",
    "        l = c.most_common()\n",
    "        l.reverse()\n",
    "        for _, count in l:\n",
    "            if k >= count:\n",
    "                result -= 1\n",
    "                k -= count\n",
    "            else:\n",
    "                break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        group = collections.Counter(arr)\n",
    "        freq = group.most_common()[::-1]\n",
    "        ans = len(freq)\n",
    "        for _, occ in freq:\n",
    "            if k >= occ:\n",
    "                ans -= 1\n",
    "                k -= occ\n",
    "            else:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        group = collections.Counter(arr)\n",
    "        freq = group.most_common()[::-1]\n",
    "        ans = len(freq)\n",
    "        for _,occ in freq:\n",
    "            if k>=occ:\n",
    "                k -= occ\n",
    "                ans -= 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        group = collections.Counter(arr)\n",
    "        freq = group.most_common()[::-1]\n",
    "        ans = len(freq)\n",
    "        for _, occ in freq:\n",
    "            if k >= occ:\n",
    "                ans -= 1\n",
    "                k -= occ\n",
    "            else:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        freq = {}     \n",
    "        for num in arr:         \n",
    "            if num not in freq:             \n",
    "                freq[num] = 1         \n",
    "            else:             \n",
    "                freq[num] += 1          \n",
    "        sorted_freq = sorted(freq.items(), key=lambda x: x[1])          \n",
    "        count = len(sorted_freq)    \n",
    "        for _, freq in sorted_freq:        \n",
    "            if k >= freq:             \n",
    "                k -= freq             \n",
    "                count -= 1         \n",
    "            else:             \n",
    "                break          \n",
    "        return count \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        cnt = {}\n",
    "        for i in arr:\n",
    "            cnt[i] = cnt.get(i, 0)+1\n",
    "        res = sorted(cnt.items(), key=lambda item: item[1])\n",
    "        # print(res)\n",
    "        i = 1\n",
    "        k -= res[0][1]\n",
    "        while k>0 and i < len(res):\n",
    "            k -= res[i][1]\n",
    "            i+=1\n",
    "        # print(i, res)\n",
    "        if k == 0 and i <= len(res):\n",
    "            i+=1\n",
    "        return len(res[i-1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        num_dict = {}\n",
    "        for i in arr:\n",
    "            if i in num_dict.keys():\n",
    "                num_dict[i] += 1\n",
    "            else:\n",
    "                num_dict[i] = 1\n",
    "        # print(num_dict)\n",
    "        sorted_list = sorted(num_dict.items(), key=lambda x: x[1])\n",
    "\n",
    "        new_list = []\n",
    "        for key, value in sorted_list:\n",
    "            for j in range(value):\n",
    "                new_list.append(key)\n",
    "\n",
    "        return len(set(new_list[k:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        cnt = collections.Counter(arr)\n",
    "        alist = list(cnt.items())\n",
    "        alist.sort(key=lambda x : x[1])\n",
    "        t = 0\n",
    "        i = 0\n",
    "        while i < len(alist) and t < k:\n",
    "            if  t + alist[i][1] > k:\n",
    "                break\n",
    "            t += alist[i][1]\n",
    "            i += 1\n",
    "        return len(alist) - i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dic = {}\n",
    "        for num in arr:\n",
    "            dic[num] = dic.get(num, 0) + 1\n",
    "        \n",
    "        dic = sorted(dic.items(), key=lambda x:x[1])\n",
    "\n",
    "        count = 0\n",
    "        n = len(dic)\n",
    "        for _, val in dic:\n",
    "            k -= val\n",
    "            if k >= 0:\n",
    "                 count += 1\n",
    "            else:\n",
    "                break\n",
    "        return n - count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        sorted_cnt = sorted(cnt.items(), key=lambda x:(-x[1]))\n",
    "        print(sorted_cnt)\n",
    "        for i in range(len(sorted_cnt)-1, -1, -1):\n",
    "            if sorted_cnt[i][1] <= k:\n",
    "                k -= sorted_cnt[i][1]\n",
    "                sorted_cnt.pop()\n",
    "            else:\n",
    "                break\n",
    "        return len(set(sorted_cnt))\n",
    "\n",
    "'''\n",
    "按照元素数量从少到多的顺序移除元素\n",
    "\n",
    "然后计算剩余元素的len(set(res))\n",
    "\n",
    "使用二维数组计数即可\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        from collections import Counter\n",
    "\n",
    "        lens = len(set(arr))\n",
    "        arr = sorted(Counter(arr).items(), key = lambda x:x[1])\n",
    "        \n",
    "        for key, v in arr:\n",
    "            if v > k:\n",
    "                return lens\n",
    "\n",
    "            else:\n",
    "                k -= v\n",
    "                lens -= 1\n",
    "        return lens\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        buckets = [[] for _ in range(len(arr) + 1)]\n",
    "        counter = collections.Counter(arr)\n",
    "        for key, count in counter.items():\n",
    "            buckets[count].append(key)\n",
    "        for count in range(len(arr) + 1):\n",
    "            if k == 0: break\n",
    "            while buckets[count] and k >= count:\n",
    "                del counter[buckets[count].pop()]\n",
    "                k -= count\n",
    "        return len(counter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        buckets = [[] for _ in range(len(arr) + 1)]\n",
    "        counter = collections.Counter(arr)\n",
    "        for key, count in counter.items():\n",
    "            buckets[count].append(key)\n",
    "        for count in range(len(arr) + 1):\n",
    "            if k == 0: break\n",
    "            while buckets[count] and k >= count:\n",
    "                del counter[buckets[count].pop()]\n",
    "                k -= count\n",
    "        return len(counter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        num_set = set(arr)\n",
    "        mydic = dict()\n",
    "        for ele in num_set:\n",
    "            mydic[ele] = 0\n",
    "        for num in arr:\n",
    "            mydic[num] += 1\n",
    "        counts = []\n",
    "        for _ke in mydic:\n",
    "            counts.append(mydic[_ke])\n",
    "        counts = sorted(counts, reverse=False)\n",
    "        tmp = k\n",
    "        for i in range(len(counts)):\n",
    "            tmp -= counts[i]\n",
    "            if tmp < 0:\n",
    "                return len(counts) - i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        # import collections\n",
    "        # cts = list(collections.Counter(arr).values())\n",
    "        # cts.sort(reverse=True)\n",
    "        # while k:\n",
    "        #     cts[-1] = cts[-1]-1\n",
    "        #     if cts[-1] <= 0:\n",
    "        #         del cts[-1]\n",
    "        #     k -= 1\n",
    "        # return len(cts)\n",
    "\n",
    "        group = collections.Counter(arr)\n",
    "        freq = group.most_common()[::-1]\n",
    "        ans = len(freq)\n",
    "        for _,occ in freq:\n",
    "            if k >= occ:\n",
    "                ans -= 1\n",
    "                k -= occ\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        group = Counter(arr) \n",
    "        freq = group.most_common()[::-1] \n",
    "        ans = len(freq) \n",
    "        for _ , occ in freq :\n",
    "            if k >= occ :\n",
    "                ans -= 1 \n",
    "                k -= occ \n",
    "            else :\n",
    "                break \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        if k>len(arr):\n",
    "            return 0\n",
    "        dic = Counter(arr)\n",
    "        lst = sorted(dic.items(),key = lambda x :x[1])\n",
    "        for i in range(len(lst)):\n",
    "            k-=lst[i][1]\n",
    "            if k<=0:\n",
    "                break  \n",
    "        return len(lst[i:]) if k<0 else len(lst[i+1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        d={}\n",
    "        for i in arr:\n",
    "            if i not in d:\n",
    "                d[i]=1\n",
    "            else:\n",
    "                d[i]+=1\n",
    "        d=sorted(d.items(),key = lambda x:x[1],reverse=False)\n",
    "        res=len(d)\n",
    "        for i,v in d:\n",
    "            if k>=v:\n",
    "                res-=1\n",
    "                k-=v\n",
    "            else:\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        d={}\n",
    "        for i in arr:\n",
    "            if i not in d:\n",
    "                d[i]=1\n",
    "            else:\n",
    "                d[i]+=1\n",
    "        d=sorted(d.items(),key = lambda x:x[1],reverse=False)\n",
    "        res=len(d)\n",
    "        for i,v in d:\n",
    "            if k>=v:\n",
    "                res-=1\n",
    "                k-=v\n",
    "            else:\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        d={}\n",
    "        for i in arr:\n",
    "            if i not in d:\n",
    "                d[i]=1\n",
    "            else:\n",
    "                d[i]+=1\n",
    "        d=sorted(d.items(),key = lambda x:x[1],reverse=False)\n",
    "        res=len(d)\n",
    "        for i,v in d:\n",
    "            if k>=v:\n",
    "                res-=1\n",
    "                k-=v\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for x in arr:\n",
    "            dic[x] += 1\n",
    "        num_freq = list(dic.items())\n",
    "        num_freq.sort(key = lambda x: x[1])\n",
    "\n",
    "        res = len(dic)\n",
    "        for num, freq in num_freq:      #贪心，先消耗掉freq小的。容易，划算\n",
    "            if freq <= k:\n",
    "                k -= freq\n",
    "                res -= 1\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        counter = defaultdict(int)\n",
    "        for it in arr:\n",
    "            counter[it] += 1\n",
    "        items = list(counter.items())\n",
    "        # print(items)\n",
    "        items.sort(key=lambda x: x[1])\n",
    "        # print(items, k)\n",
    "        for i, cnt in enumerate(items):\n",
    "            if cnt[1] <= k:\n",
    "                k -= cnt[1]\n",
    "            else:\n",
    "                return len(items) - i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        data = Counter(arr)\n",
    "        data = sorted(data.items(), key = lambda x: x[1])\n",
    "        data = [list(i) for i in data]\n",
    "        len_num = 0\n",
    "        for i, r in enumerate(data):\n",
    "            len_num += r[1]\n",
    "            if len_num == k:\n",
    "                return len(data) - i - 1\n",
    "            elif len_num > k:\n",
    "                return len(data) - i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dict = {}\n",
    "        for tmp in arr:\n",
    "            if tmp in dict.keys():\n",
    "                dict[tmp] += 1\n",
    "            else:\n",
    "                dict[tmp] = 1\n",
    "        \n",
    "        lst = sorted([[v,t] for t,v in dict.items()])\n",
    "        print(lst)\n",
    "        x = 0\n",
    "        idx = k\n",
    "        while x < k:\n",
    "            if idx >= lst[x][0]:\n",
    "                idx -= lst[x][0]\n",
    "                lst[x][0] = 0\n",
    "            else:\n",
    "                break \n",
    "            x += 1\n",
    "        print(lst)\n",
    "        return len([v for v in lst if v[0] != 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        z = dict(Counter(arr))\n",
    "\n",
    "        z = sorted(z.items(),key=lambda x:x[1],reverse=False)\n",
    "        z = dict(z)\n",
    "        res = copy.deepcopy (z)\n",
    "        for key in z:\n",
    "            if z[key] <= k:\n",
    "                k -= z[key]\n",
    "                del res[key]\n",
    "            elif z[key] > k:\n",
    "                break\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        from collections import Counter\n",
    "        nums = Counter(arr)\n",
    "        print(nums)\n",
    "        nums = sorted(nums.items(), key = lambda x:x[1])\n",
    "        print(nums)\n",
    "        res = set()\n",
    "        for k1, v in nums:\n",
    "            if k <= 0:\n",
    "                res.add(k1)\n",
    "            else:\n",
    "                k -= v\n",
    "                if k < 0:\n",
    "                    res.add(k1)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        counts = {}\n",
    "        for num in arr:\n",
    "            counts[num] = counts.get(num, 0) + 1\n",
    "        \n",
    "        heap = []\n",
    "        for num, count in counts.items():\n",
    "            heapq.heappush(heap, (count, num))\n",
    "        \n",
    "        for _ in range(k):\n",
    "            if heap[0][0] > 1:\n",
    "                heap[0] = (heap[0][0] - 1, heap[0][1])\n",
    "            else:\n",
    "                heapq.heappop(heap)\n",
    "        \n",
    "        return len(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        h = []\n",
    "        c = Counter(arr)\n",
    "        for num, freq in c.items():\n",
    "            heapq.heappush(h, (freq, num))\n",
    "        \n",
    "        while k:\n",
    "            freq, num = heapq.heappop(h)\n",
    "            if freq > 1:\n",
    "                heapq.heappush(h, (freq - 1, num))\n",
    "            k -= 1\n",
    "        \n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        counts = {}\n",
    "        for num in arr:\n",
    "            counts[num] = counts.get(num, 0) + 1\n",
    "        \n",
    "        heap = [(count, num) for num, count in counts.items()]\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        while heap:\n",
    "            count = heap[0][0]\n",
    "            if k >= count:\n",
    "                k -= count\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return len(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq \n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int: \n",
    "        count = collections.defaultdict(int)\n",
    "\n",
    "        for num in arr:\n",
    "            count[num]+=1 \n",
    "\n",
    "        heap = [] \n",
    "        for num, freq in count.items():\n",
    "            heapq.heappush(heap, (freq, num))\n",
    "        \n",
    "        while heap:\n",
    "            freq, num = heap[0]\n",
    "            if k>=freq:\n",
    "                k-=freq\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break \n",
    "\n",
    "        return len(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dic = dict()\n",
    "        for a in arr:\n",
    "            if a in dic.keys():\n",
    "                dic[a] = dic[a] + 1\n",
    "            else:\n",
    "                dic[a] = 1\n",
    "\n",
    "        ls = sorted(dic.items(), key=lambda kv: (kv[1], kv[0]))\n",
    "        # for l in ls[:]:\n",
    "        #     while (k > 0 and l[1] > 0):\n",
    "        #         l = (l[0], l[1] - 1)\n",
    "        #         k = k - 1\n",
    "        #     if l[1] == 0:\n",
    "        #         ls.pop(0)\n",
    "        #     if k == 0:\n",
    "        #         break\n",
    "        # return len(ls)\n",
    "        for i,l in enumerate(ls):\n",
    "            k-=l[1]\n",
    "            if k==0:\n",
    "                return len(ls) - (i + 1)\n",
    "            elif k<0:\n",
    "                return len(ls) - i\n",
    "        return 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dic = dict()\n",
    "        for a in arr:\n",
    "            if a in dic.keys():\n",
    "                dic[a] = dic[a] + 1\n",
    "            else:\n",
    "                dic[a] = 1\n",
    "\n",
    "        ls = sorted(dic.items(), key=lambda kv: (kv[1], kv[0]))\n",
    "        for l in ls[:]:\n",
    "            while (k > 0 and l[1] > 0):\n",
    "                l = (l[0], l[1] - 1)\n",
    "                k = k - 1\n",
    "            if l[1] == 0:\n",
    "                ls.pop(0)\n",
    "            if k == 0:\n",
    "                break\n",
    "        return len(ls)\n",
    "\n",
    "        \n",
    "\n",
    "        # values = list(dic.values())\n",
    "        # values.sort()\n",
    "\n",
    "        # tmp = []\n",
    "        # for v in values:\n",
    "        #     for (key,value) in dic.items():\n",
    "        #         if value == v:\n",
    "        #             for i in range(v):\n",
    "        #                 tmp.append(key)\n",
    "        #             dic.pop(key)\n",
    "        #             break\n",
    "        # return len(set(tmp[k:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dictLis = {}\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in dictLis.keys():\n",
    "                dictLis[arr[i]] = 1\n",
    "            else:\n",
    "                dictLis[arr[i]] += 1\n",
    "        dictLis = sorted(dictLis.items(), key = lambda kv:(kv[1], kv[0]))\n",
    "        # print(dictLis)\n",
    "        l = len(dictLis)\n",
    "        for item in dictLis:\n",
    "            print(item)\n",
    "            if k >= item[1] :\n",
    "                k -= item[1]\n",
    "                # print(item[0],dictLis[0])\n",
    "                l -= 1\n",
    "            else:\n",
    "                # print(dictLis)\n",
    "                break\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        set_arr = set(arr)\n",
    "        sort_arr = list(set_arr)\n",
    "        sort_arr.sort() \n",
    "        if len(arr) == len(set_arr):\n",
    "            return len(arr)-k\n",
    "        if k == len(arr):\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return len(set_arr)\n",
    "        group = collections.Counter(arr)\n",
    "        freq = group.most_common()[::-1]\n",
    "        ans = len(freq)\n",
    "        for _, occ in freq:\n",
    "            if k >= occ:\n",
    "                ans -= 1\n",
    "                k -= occ\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        \n",
    "        mp = {}\n",
    "        for x in arr:\n",
    "            mp[x] = mp.get(x, 0) + 1\n",
    "        \n",
    "        mp = sorted(mp.items(), key = lambda item: (item[1], item[0]))\n",
    "    \n",
    "        \n",
    "        print(mp)\n",
    "        \n",
    "        mp2 = mp.copy()\n",
    "        for val, count in mp2:\n",
    "            print(val, count)\n",
    "            if count <= k:\n",
    "                k -= count\n",
    "                print(k)\n",
    "                mp.remove((val, count))\n",
    "            if count > k or k == 0:\n",
    "                break\n",
    "        \n",
    "        return len(mp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        c = Counter(arr)\n",
    "        d = dict(c)\n",
    "        s = sorted(d.items(), key=lambda x:x[1])\n",
    "        for item in s:\n",
    "            if d[item[0]] > 0:\n",
    "                while d[item[0]] >0 and k>0:\n",
    "                    d[item[0]] -= 1\n",
    "                    k-=1\n",
    "            if k == 0:\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "        return len([v for k,v in d.items() if v >0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        if not arr or len(arr) == k:\n",
    "            return 0\n",
    "        \n",
    "        def _convert_list(l):\n",
    "            from collections import OrderedDict\n",
    "            od = OrderedDict()\n",
    "            for item in l:\n",
    "                if item in od:\n",
    "                    od[item] += 1\n",
    "                else:\n",
    "                    od[item] = 1\n",
    "            new_list = sorted(od.items(), key=lambda x: x[1])\n",
    "            return new_list\n",
    "        \n",
    "        new_arr = _convert_list(arr)\n",
    "        # print(new_arr)\n",
    "        index = 0\n",
    "        for item, item_count in new_arr:\n",
    "            k = k - item_count\n",
    "            # print(f\"index: {index}, last: {k}\")\n",
    "            if k > 0:\n",
    "                index += 1\n",
    "                continue\n",
    "            elif k == 0:\n",
    "                return len(new_arr) - (index + 1)\n",
    "            else:\n",
    "                return len(new_arr) - index\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        counter=Counter(arr)\n",
    "        arr.sort(key=lambda x:(counter[x],x))\n",
    "        return len(Counter(arr[k:]))\n",
    "\n",
    "    # def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "    #     group = collections.Counter(arr)\n",
    "    #     freq = group.most_common()[::-1]\n",
    "    #     ans = len(freq)\n",
    "    #     for _, occ in freq:\n",
    "    #         if k >= occ:\n",
    "    #             ans -= 1\n",
    "    #             k -= occ\n",
    "    #         else:\n",
    "    #             break\n",
    "    #     return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        c = Counter(arr)\n",
    "        d = dict(c)\n",
    "        s = sorted(d.items(), key=lambda x:x[1])\n",
    "        for item in s:\n",
    "            if d[item[0]] > 0:\n",
    "                while d[item[0]] >0 and k>0:\n",
    "                    d[item[0]] -= 1\n",
    "                    k-=1\n",
    "            if k == 0:\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "        return len([v for k,v in d.items() if v >0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        if not arr or len(arr) == k:\n",
    "            return 0\n",
    "        \n",
    "        def _convert_list(l):\n",
    "            from collections import OrderedDict\n",
    "            od = OrderedDict()\n",
    "            for item in l:\n",
    "                if item in od:\n",
    "                    od[item] += 1\n",
    "                else:\n",
    "                    od[item] = 1\n",
    "            new_list = sorted(od.items(), key=lambda x: x[1])\n",
    "            return new_list\n",
    "        \n",
    "        new_arr = _convert_list(arr)\n",
    "        print(new_arr)\n",
    "        index = 0\n",
    "        for item, item_count in new_arr:\n",
    "            k = k - item_count\n",
    "            print(f\"index: {index}, last: {k}\")\n",
    "            if k > 0:\n",
    "                index += 1\n",
    "                continue\n",
    "            elif k == 0:\n",
    "                return len(new_arr) - (index + 1)\n",
    "            else:\n",
    "                return len(new_arr) - index\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        a=collections.Counter(arr)\n",
    "        arr.sort(key=lambda x:(a[x],x))\n",
    "        return len(set(arr[k:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        arr.sort(key=lambda x:(cnt[x],x))\n",
    "        # print(arr)\n",
    "        return len(set(arr[k:]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        count = Counter(arr)\n",
    "        total = set(count)\n",
    "        count = sorted(list(count.items()), key=lambda x:x[1])\n",
    "        i, n = 0, len(total)\n",
    "        while i < n and k > 0:\n",
    "            k -= count[i][1]\n",
    "            if k >= 0:\n",
    "                total.remove(count[i][0])\n",
    "            i += 1\n",
    "        return len(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "    #   listint=list(map(int,arr.split(\",\")))\n",
    "      c=Counter(arr)\n",
    "      intcount=dict(c)\n",
    "    #   intcount={}#空字典\n",
    "    #   for i in arr:\n",
    "    #       intcount[i]=arr.count(i)#统计个数写入字典\n",
    "      items=[]\n",
    "      for m,n in intcount.items():\n",
    "          items.append([m,n])\n",
    "      items.sort(key=lambda x:x[1],reverse=False)\n",
    "      n=len(items)\n",
    "      for i in range (0,n):\n",
    "          if items[i][1]<=k:\n",
    "             n=n-1\n",
    "             k=k-items[i][1]\n",
    "          else:\n",
    "              break\n",
    "      return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr, k):\n",
    "        map = {}\n",
    "        for i in arr:            \n",
    "            if  i in map:\n",
    "                map[i] += 1\n",
    "            else:\n",
    "                map[i] = 1\n",
    "\n",
    "        map = sorted(map.items(), key = lambda kv:(kv[1], kv[0]))\n",
    "        print(map)\n",
    "        count = 0\n",
    "        for i in range(len(map)):\n",
    "            print(map[i])\n",
    "\n",
    "            if k >= map[i][1]:\n",
    "                k -= map[i][1]\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        print(map)\n",
    "        return len(map) - count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "\n",
    "        freq = collections.Counter(arr)\n",
    "        freq = sorted(freq.items(), key = lambda kv:(kv[1], kv[0]))\n",
    "        res = len(freq)\n",
    "\n",
    "        for key, value in freq:\n",
    "            if k - value >= 0:\n",
    "                res -= 1\n",
    "                k = k - value\n",
    "            else:\n",
    "                return res\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        map={}\n",
    "        for n in arr:\n",
    "            map[n] = map.get(n,0) + 1\n",
    "        lst = sorted(map.items(), key=lambda kv: (kv[1], kv[0]), reverse=False)\n",
    "        l = len(map)\n",
    "        for up in lst:\n",
    "            if up[1] <= k:\n",
    "                l-=1\n",
    "                k-=up[1]\n",
    "            else:\n",
    "                break\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        dic = {}\n",
    "        for num in arr:\n",
    "            if num not in dic:\n",
    "                dic[num] = 1\n",
    "            else:\n",
    "                dic[num] += 1\n",
    "        dic = sorted(dic.items(), key = lambda kv:(kv[1], kv[0]))\n",
    "        flag = 0\n",
    "        while k:\n",
    "            if k >= dic[flag][1]:\n",
    "                k -= dic[flag][1]\n",
    "                flag += 1\n",
    "            else:\n",
    "                k = 0\n",
    "        return len(dic) - flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        counter = Counter(arr)\n",
    "        # print(counter)\n",
    "        arr.sort(key=lambda x:(counter[x], x))\n",
    "        # print(arr)\n",
    "        return len(set(arr[k:]))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:\n",
    "        a=collections.Counter(arr)\n",
    "        arr.sort(key=lambda x:(a[x],x))\n",
    "        return len(set(arr[k:]))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
